package Demo1;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-08-22
 * Time: 15:26
 */
public class Test {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
    }

    public Stack<Integer> stack1 = new Stack<Integer>();
    public Stack<Integer> stack2 = new Stack<Integer>();

    public int findMax(int val){
        while(val != stack1.peek() && !stack1.isEmpty()){
            stack2.push(stack1.pop());
        }

        int flag = -1;
        while(!stack2.isEmpty()){
            int value = stack2.pop();
            if(value > val && flag == -1){
                flag = value;
            }
            stack1.push(value);
        }
        return flag;
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length];
        int j = 0;
        for(int i = 0;i < nums2.length;i++){
            stack1.push(nums2[i]);
        }

        for(int i = 0;i < nums1.length;i++){
            ret[j++] = findMax(nums1[i]);
        }
        return ret;
    }
    public ListNode MergedLinkedList(ListNode s1,ListNode s2){
        //判空
        if(s1 == null && s2 != null){
            return s2;
        }else if(s1 != null && s2 == null){
            return s1;
        }else if(s1 == null && s2 == null){
            return s2;
        }

        //都不为空，先找两条链表最小值，判段头节点是谁
        ListNode head = null;
        ListNode cur1 = s1;
        ListNode cur2 = s2;
        if(cur1.val <= cur2.val){
            head = cur1;
            cur1 = cur1.next;
        }else{
            head = cur2;
            cur2 = cur2.next;
        }

        //合并链表
        ListNode prev = head;//用来标记前一个节点
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }

        if(cur1 != null){
            prev.next = cur1;
        }

        if(cur2 != null){
            prev.next = cur2;
        }

        return head;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        for(int i = 0;i < lists.length - 1;i++){
            lists[i + 1] =  MergedLinkedList(lists[i],lists[i + 1]);
        }
        return lists[lists.length - 1];
    }
    public static void main(String[] args) {
        Test test = new Test();
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        int[] ret = new int[nums1.length];
        ret = test.nextGreaterElement(nums1,nums2);
        System.out.println(Arrays.toString(ret));
    }
}
